//
//  main.swift
//  数据结构与算法
//
//  Created by Rowling on 2024/2/22.
//

import Foundation

func spaceStr(count : Int, spaceLong : Int) -> String {
    var s = ""
    for _ in 0 ..< count {
        for _ in 0 ..< spaceLong {
            s.append(" ")
        }
    }
    return s
}

func printTree(info : [[Node<Int>?]]) {
    let level = info.count
    let width = 5
    let space = 1
    for i in 0 ..< info.count {
        let layerArray = info[i]
        let maxLevel = info.count
        let maxLong = Int(pow(2, Double(level - 1))) * (width + space) - 1
        let foo = Int(pow(2, Double(level - 1 - i))) * (width + space) - 1
        let headSpace = (foo - width) / 2
        let currentLineLong = maxLong - headSpace * 2
        let currentLineCount = layerArray.count

        var str = spaceStr(count: headSpace, spaceLong: space)
        var numSpace = i == 0 ? 0 : ((currentLineLong - currentLineCount * width) / (currentLineCount - 1)) * space
        var numSpaceStr = spaceStr(count: numSpace, spaceLong: space)
        for i in 0 ..< currentLineCount {
            let node = layerArray[i]
            if i != 0 {
                str.append(numSpaceStr)
            }
            if node != nil {
//                str.append(String(format: "%02d-%02d-%d", 
//                                  node!.element,
//                                  node?.parent?.element ?? 0,
//                                  (node as? AVLNode)?.height ?? 0))
//                str.append(String(format: "%02d_(%02d)",
//                                  node!.element, node?.parent?.element ?? 0))
                
                // rb tree
                // 🟥⬛️ -- complex
//                str.append(String(format: "%02d-%02d%@",
//                                  node!.element,
//                                  node?.parent?.element ?? 0,
//                                  (node as? RBNode)?.color == BLACK ? "⬛️" : "🟥"))
                
                // 🟥⬛️ -- simple
                str.append(String(format: "%02d_%@",
                                  node!.element,
                                  (node as? RBNode)?.color == BLACK ? "⬛️" : "🟥"))
//                str.append(String(format: "%02d_(%02d)",
//                                  node!.element, node?.parent?.element ?? 0))
            } else {
                for _ in 0 ..< width {
                    str.append("·")
                }
            }
        }
        print(str)
    }
    print("-----------------------------------")
}

func binarySearchTree() {
    let tree = BinarySearchTree<Int>()

    //let a = [7, 4, 9, 2, 5, 8, 11, 1, 3, 10, 12]
    //let a = [8, 4, 13, 2, 6, 8, 10, 1, 3, 5, 7, 9, 12, 11]
    //let a = [2, 1, 3]
    //let a = [7, 4, 9, 5]
//    let a = [7, 4, 9, 2, 5, 8, 11, 3, 12, 1]
    let a = [8, 7, 9, 6, 10, 5, 11]
    //let a = [5, 2, 6, 1, 4, 3]

    for i in a {
        tree.add(element: i)
    }
    //print(tree.front())
    //tree.levelorderTraversal { e in
    //    print(e)
    //    return e == 4
    //}
    //print(tree.postorderTraversal())
    //print(tree.levelorderTraversal())
    //print(tree.size)
    //print("树的层级:\(tree.getLayerCount())")
    //print("树的层级数据:\(tree.printInfo())")
    printTree(info: tree.printInfo())
    //print("树的层级数据:\(tree.printTree())")
    //let b = 15
    //for i in 0 ..< b {
    //
    //}
    //print("   2")
    //print(" X   3")
    //print("X 3 1 2")
    //print("X 3")
    //print("X 3")
    // 二叉树高度
    //print("树的层级数据:\(tree.height())")
    //print("是否是完全二叉树:\(tree.isComplete())")

    // 翻转二叉树
    //tree.reverseTree()
    //printTree(info: tree.printInfo())

    // 前驱节点
    //print("前驱节点:\(tree.predecessor(no: tree.root!)?.element)")
    //tree.levelorderTraversal { e in
    //    if e == 9 {
    //        return true
    //    }
    //    return false
    //}

    // 移除
    //tree.remove(element: 12)
    //tree.remove(element: 13)
    //print("-------------")
    //printTree(info: tree.printInfo())
    //tree.remove(element: 9)
    //print("-------------")
    //printTree(info: tree.printInfo())
    //tree.remove(element: 10)
    //print("-------------")
    //printTree(info: tree.printInfo())
    //tree.remove(element: 11)
    //print("-------------")
    //printTree(info: tree.printInfo())
    //tree.remove(element: 12)
    //print("-------------")
    //printTree(info: tree.printInfo())
    tree.remove(element: 11)
    print("-------------")
    printTree(info: tree.printInfo())
}


//MARK: -- AVL Tree
func avlTree() {
    let tree = AVLTree<Int>()
//    let a = [13, 14, 15, 12, 11, 17, 16, 8, 9, 1]
//    let a = [8, 7, 9, 6, 10, 5, 11]
    let a = [85, 19, 69, 3, 7, 99, 95, 2, 1, 70, 44, 58, 11, 21, 14, 93, 57, 4, 56]
    for i in a {
        tree.add(element: i)
//        printTree(info: tree.printInfo())
    }
    printTree(info: tree.printInfo())
    
//    tree.remove(element: 14)
//
//    tree.remove(element: 8)
//    printTree(info: tree.printInfo())
    for i in a {
        tree.remove(element: i)
        print("移除\(i)")
        printTree(info: tree.printInfo())
    }

}
//avlTree()


func rbTree() {
    let tree = RBTree<Int>()
    
    let a = [55, 87, 56, 74, 96, 22, 62, 20, 70, 68, 90, 50]
    for i in a {
        tree.add(element: i)
//        printTree(info: tree.printInfo())
    }
    printTree(info: tree.printInfo())
    
    for i in a {
        tree.remove(element: i)
        print("移除\(i)")
        printTree(info: tree.printInfo())
    }
}
rbTree()


